import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
// https://leetcode.cn/problems/permutations-ii/
public class PermuteUnique {
    class Solution {

        private List<List<Integer>> res = new ArrayList<>();
        private boolean [] state ;
        public List<List<Integer>> permuteUnique(int[] nums) {
            state = new boolean[nums.length];
            Arrays.sort(nums);
            backTracking(new ArrayList<>(),nums);
            return res;
        }

        private void backTracking(List<Integer> path , int [] nums)
        {
            if(path.size() == nums.length)
            {
                res.add(new ArrayList<>(path));
                return ;
            }
            HashSet<Integer> set = new HashSet<>();
            for(int i = 0 ; i < nums.length ; i ++)
            {
                if(!state[i] && !set.contains(nums[i]))
                {
                    state[i] = true;
                    path.add(nums[i]);
                    set.add(nums[i]);
                    backTracking(path,nums);
                    path.remove(path.size()-1);
                    state[i] = false;

                }
            }


        }
    }
}
